//
// Created by ASUS on 2023/9/20.
//
//埃氏筛

#include <bits/stdc++.h>
using namespace std;
//埃氏筛
const int MX=1e5+1;
int vis[MX+1]; //vis[x]=0说明是质数

int init=[](){
	memset(vis,0,sizeof vis);
	vis[0]= 1,vis[1]=1;
	for(int i=2;i*i<=MX;i++){
		if(!vis[i]){
			for (int j=i*i;j<=MX;j+=i){
				vis[j]= true;
			}
		}
	}
	return 0;
}();


//欧拉筛
//const int MX=1e5+1;
//vector<int> primes;
//bool vis[MX+1];
//int init=[](){
//	vis[0]=vis[1]=true;
//	for(int i=2;i<=MX;i++){
//		if(!vis[i]) primes.push_back(i);
//		for (int j : primes) {
//			if (i * j > MX) break;
//			vis[i * j] = true;
//			if (i % j == 0) {
//				break;
//			}
//		}
//	}
//	return 0;
//}();